package com.leetcode.根据数据结构分类.链表;

import com.leetcode.datastructure.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: ZhouBert
 * @date: 2021/2/18
 * @description: 25. K 个一组翻转链表
 * https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
 * 我能写出 循环的链表反转；
 * 递归的有点苗头，但是等好好琢磨。
 */
public class C_25_K个一组翻转链表 {

	public static void main(String[] args) {
		C_25_K个一组翻转链表 action = new C_25_K个一组翻转链表();
		test1(action);
		test2(action);
	}

	public static void test1(C_25_K个一组翻转链表 action) {
		// 1
		ListNode head = new ListNode(1);
		head.next = new ListNode(2);
		head.next.next = new ListNode(3);
		head.next.next.next = new ListNode(4);
		head.next.next.next.next = new ListNode(5);
		int k = 3;
		ListNode res = action.reverseKGroup(head, k);
		System.out.println("res = " + res.toString());
	}

	public static void test2(C_25_K个一组翻转链表 action) {
		// 1
		ListNode head = new ListNode(1);
		head.next = new ListNode(2);
		int k = 2;
		ListNode res = action.reverseKGroup(head, k);
		System.out.println("res = " + res.toString());
	}


	/**
	 * 理解题意：
	 * 1.K 个一组进行翻转
	 * 2.最后的数组如果不到k 就保持
	 * --
	 * 先用我的笨方法吧
	 *
	 * @param head
	 * @param k
	 * @return
	 */
	public ListNode reverseKGroup(ListNode head, int k) {
		if (head == null || head.next == null) {
			//边界判断
			return head;
		}
		ListNode curNode = head, prev = null, nextNode = curNode.next;
		//使用 List 存放每一组
		List<ListNode> list = new ArrayList<>();
		int count = 0;
		while (curNode != null) {
			while (curNode != null) {
				curNode.next = prev;
				prev = curNode;
				curNode = nextNode;
				if (nextNode != null) {
					nextNode = nextNode.next;
				}


				//此时已经完成了一个元素的反转
				count++;

				if (count == k) {
					//如果够反转一组
					list.add(prev);

					prev = null;
					break;
				}
			}

			//如果不够反转一组，就再反转回来
			if (count < k) {
				//此时 prev 就是反转后的头节点
				curNode = prev;
				prev = null;
				nextNode = curNode.next;
				while (curNode!=null){
					curNode.next = prev;
					prev = curNode;
					curNode = nextNode;
					if (nextNode != null) {
						nextNode = nextNode.next;
					}
				}
				list.add(prev);
			}
			count = 0;
		}

		//将 list 中的答案汇总
		head = list.get(0);
		curNode = head;
		prev = null;
		while (curNode != null) {
			prev = curNode;
			curNode = curNode.next;
		}
		//此时 prev 就是 上一个的 tail 节点

		for (int i = 1; i < list.size(); i++) {
			curNode = list.get(i);
			prev.next = curNode;
			prev = null;
			while (curNode != null) {
				prev = curNode;
				curNode = curNode.next;
			}
			//此时 curNode 遍历到底
		}

		return head;


	}
}
